Compaq 1996 Problema 1
Cel mai mare hambar

  Un fermier vrea sa construiasca un hambar in perimetrul fermei sale si vrea
ca acesta sa siba o arie cat mai mare. Dar in ferma sa exista si arbori si
alte cladiri, iar el nu vrea ca toate acestea sa fie afectate in vreun fel de
hambar. Pentru simplitate, ferma este reprezentata ca o matrice cu m linii si
n coloane, cu una sau mai multe zone ocupate deja de obstacolele mentionate
anterior. Hambarul, de forma dreptunghiulara, nu trebuie sa se atinga de nici
o alta cladire sau de vreun copac.
  In exemplul urmator, consideram o ferma de dimensiunea 5*6:
  123456
 1XX
 2
 3
 4   XXX
 5   XXX
  Hambarul poate fi in acest caz:
  123456
 1XX BBB
 2   BBB
 3
 4   XXX
 5   XXX
  sau
  123456
 1XX
 2
 3BB
 4BB XXX
 5BB XXX

  In aceste cazuri, hambarul se afla intre coordonatele (1,4) si (2,6) in
prima varianta, respectiv intre (3,1)si (5,2) in a doua varianta. In ambele
variante, hambarul ocupa o suprafata de 6.
  Se cere sa se determine aria celui mai mare hambar si numarul total de
locatii in care poate fi amplasat acel hambar.
  Se vor citi din fisierul HAMBAR.IN un numar nespecificat de seturi de date
de intrare. Un set de date va incepe cu o linie ce va contine numarul de
obstacole (copaci, cladiri etc.) din ferma reprezentata de acest set. A doua
linie va contine inaltimea si latimea fermei. Urmatoarele linii vor contine,
fiecare, linia, coloana, inaltimea si latimea fiecarui obstacol. Setul de date
se va termina cu o linie continand un numar negativ.
  Va exista cel putin un set de date, iar fiecare set va contine cel putin
cate un obstacol. Fisierul de intrare pentru exemplul de mai sus este:
2
5 6
1 1 1 2
4 4 2 3
-1
  Iesirea va fi facuta sub forma:
Arie maxima=###.Numarul solutiilor=###.
=======================================

Solutie (Mihai Stroe)
  Problema este o varianta modificata a enuntului clasic: "Se da o matrice
cu elemente 0 si 1. Sa se afle cel mai mare dreptunghi care nu contine nici
un 1." Rezolvarea clasica este realizata prin metoda "divide et impera": un
obstacol imparte tabla in 4 table, care nu sunt disjuncte.
  Sa evaluam complexitatea acestei metode. Consideram dreptunghiurile memorate
intr-o lista; la fiecare pas se va analiza un obstacol. Fiecare dreptunghi
care contine obstacolul va fi inlocuit in lista de 4 dreptunghiuri.
  In situatia initiala, un obstacol aflat in centru inparte tabla in 4 parti:
nord, sud, est, vest. Un al doilea obstacol (aflat, de exemplu, in NE) va
imparti in 4 partea din nord si pe cea din est. Continuand analiza, se ajunge
la o complexitate exponentiala.
  Rezolvarea mea are complexitatea n^3, in cazul cel mai defavorabil, unde n
este numarul de obstacole.
  Sa consideram matricea care reprezinta ferma. Consideram fiecare obstacol
prelungit in cele 4 directii cu cate un rand.
  Astfel, un obstacol
  12345
 1
 2 XX
 3
devine
  12345
 1XXXX
 2XXXX
 3XXXX

  Ducem paralele la axe prin varfurile fiecarui obstacol; obtinem vectorii X
si Y, care reprezinta coordonatele prin care sunt duse paralele la Y si la X.
Fiecare vector va avea maxim 2*n+2 componente (se adauga 0 si dimensiunea
fermei; unele coordonate pot coincide).
  Obtinem o noua matrice, "mai mica" sau de aceleasi dimensiuni cu cea
initiala (pe cazuri foarte rare; important este ca se poate reduce o matrice
mare (1000/1000 sau mai mare), daca are putine obstacole); A[i,j] reprezinta
aria suprafetei cuprinse intre dreptele X[i], X[i+1], Y[j] si Y[j+1]. Daca
A[i,j] este acoperita de o parte a unui obstacol, A[i,j] va deveni 0.
  Rezolvarea se bazeaza pe o parcurgere pe linii a matricei A.
  Consideram d=numarul de coloane ale matricii si Lin numarul liniei curente.
  Folosim o alta matrice: mat[i,j] reprezinta aria suprafetei maxime limitata
la stanga de y[i], la dreapta de y[j], in jos de x[Lin+1] si care nu contine
nici un obstacol. Numim "parte activa" a matricei mat elementele mat[i,j]
diferite de 0 care au proprietatea ca nu exista k,l cu k<>i, l<>j, k<=i<=j<=l
cu suprafata mat[i,j] incepand pe aceeasi linie.
  De exemplu:
A= 011103
   022216
  lin=2
  mat[2,4]=9 si (2,4) se afla in "partea activa" a matricei
  mat[2,3]=6 si (2,3) nu se afla in "partea activa" a matricei
  mat[2,6]=13 si (2,6) se afla in "partea activa" a matricei
  mat[6,6]=9 si (6,6) se afla in "partea activa" a matricei
  mat[4,6]=9 si (4,6) nu se afla in "partea activa" a matricei
  mat[1,x]=0 pentru orice x a.i. 1<=x<=6

  Elementele care nu sunt in "partea activa" sunt nule sau se pot calcula usor
din cele din partea activa.
  Memoram "partea activa" a matricei intr-o lista. Pentru fiecare linie se
analizeaza fiecare element al listei. Daca pe noua linie, intre y[i] si y[j]
se gaseste o parte dintr-un obstacol, atunci se actualizeaza valorile pentru
mat[k,l] cu i<=k<=l<=j (daca este cazul) si valorile care trec in "partea
activa" sunt introduse in lista; mat[i,j] este comparat cu optimul, apoi sters
din lista. In caz contrar, se calculeaza noua valoare pentru mat[i,j].
  In lista se pot gasi maxim d*(d+1)/2+d elemente. Fiecare linie este
analizata o singura data. Deci, complexitatea este n^3 (n=numar de obstacole)
pe cazul cel mai defavorabil; pe un caz normal, timpul de executie este foarte
mic. Fata de implementarea care lucreaza cu toata matricea mat, folosirea
partii active este foarte avantajoasa; "partea activa" este redusa fata de
intreaga matrice.

{$r+}
{$m 10000,0,655000}
uses crt;
type arr=array[0..101]of longint;
     ar=array[0..101]of ^arr;
var i,ii,jj,j,lin,nr,x1,y1,x2,nrs,opt,y2,nrx,nry,k,l,min,mp,m,n,nro:longint;
    s:string;
    fi,fo:text;
    obst:array[0..101,1..4]of longint;
    x,y:array[1..200]of longint;
    a,loc,mat:ar;
    d,v:array[0..100]of longint;
    mul:array[1..1000,1..5]of longint;
    nrteste:longint;

procedure readdata;
begin
  fillchar(x,sizeof(x),0);
  fillchar(y,sizeof(y),0);
  fillchar(obst,sizeof(obst),0);
  opt:=0;nrs:=0;
  for i:=0 to 100 do
      for j:=0 to 100 do
          begin
            a[i]^[j]:=0;
            loc[i]^[j]:=0;
            mat[i]^[j]:=0;
          end;
  readln(fi,nro);
  if nro<0 then exit;
  readln(fi,m,n);
  for i:=1 to nro do
      begin
        readln(fi,obst[i,1],obst[i,2],obst[i,3],obst[i,4]);
        obst[i,3]:=obst[i,1]+obst[i,3]-1;
        obst[i,4]:=obst[i,2]+obst[i,4]-1;
        dec(obst[i,1],2);
        dec(obst[i,2],2);
        inc(obst[i,3]);
        inc(obst[i,4]);
        if obst[i,1]<0 then obst[i,1]:=0;
        if obst[i,2]<0 then obst[i,2]:=0;
        if obst[i,3]>m then obst[i,3]:=m;
        if obst[i,4]>n then obst[i,4]:=n;
      end;
end;

procedure makexy;
begin
  x[nro*2+2]:=0;y[nro*2+2]:=0;
  x[nro*2+1]:=m;
  y[nro*2+1]:=n;
  for i:=1 to nro do
      begin
        x[2*i-1]:=obst[i,1];
        x[i*2]:=obst[i,3];
        y[2*i-1]:=obst[i,2];
        y[i*2]:=obst[i,4];
      end;
end;

procedure sort;
begin
  for i:=1 to nro*2+1 do
      begin
        min:=maxlongint;
        mp:=0;
        for j:=i to nro*2+2 do
            if x[j]<min then begin min:=x[j];mp:=j;end;
        if mp<>0 then
           begin
             x[mp]:=x[i];
             x[i]:=min;
           end;
      end;
  for i:=1 to nro*2+1 do
      begin
        min:=maxlongint;
        mp:=0;
        for j:=i to nro*2+2 do
            if y[j]<min then begin min:=y[j];mp:=j;end;
        if mp<>0 then
           begin
             y[mp]:=y[i];
             y[i]:=min;
           end;
      end;
end;

procedure constrmatr;
begin
  for i:=1 to nro*2+1 do
      if x[i]=x[i+1] then x[i]:=maxlongint;
  for i:=1 to nro*2+1 do
      if y[i]=y[i+1] then y[i]:=maxlongint;
  sort;
  nrx:=nro*2+2;
  while x[nrx]=maxlongint do
    begin
      x[nrx]:=0;
      dec(nrx);
    end;
  nry:=nro*2+2;
  while y[nry]=maxlongint do
    begin
      y[nry]:=0;
      dec(nry);
    end;
  m:=nrx-1;
  n:=nry-1;
  for i:=1 to m do
      for j:=1 to n do
          a[i]^[j]:=(x[i+1]-x[i])*(y[j+1]-y[j]);
end;

procedure fillmatr;
begin
  for i:=1 to nro do
      begin
        x1:=1;
        while x[x1]<>obst[i,1] do inc(x1);
        x2:=x1+1;
        while x[x2]<>obst[i,3] do inc(x2);
        y1:=1;
        while y[y1]<>obst[i,2] do inc(y1);
        y2:=y1+1;
        while y[y2]<>obst[i,4] do inc(y2);
        for j:=x1 to x2-1 do
            for k:=y1 to y2-1 do
                a[j]^[k]:=0;
      end;
end;

procedure makelin;
begin
  d[0]:=0;
  for i:=1 to n do
      d[i]:=d[i-1]+a[lin]^[i];
  for i:=1 to n do
      if (a[lin]^[i]<>0)and(a[lin]^[i-1]=0) then
         begin
           j:=i;
           while a[lin]^[j+1]<>0 do inc(j);
           v[i]:=j;
         end
         else v[i]:=0;
  for i:=1 to n do
      if v[i-1]>=i then
         v[i]:=v[i-1];
end;

procedure baga;
begin
  for ii:=mul[i,1] to mul[i,2] do
      if ((a[lin]^[ii-1]=0)or(ii=mul[i,1]))and(a[lin]^[ii]<>0) then
         begin
           jj:=ii;
           while (a[lin]^[jj+1]<>0)and(jj<mul[i,2]) do inc(jj);
           inc(nr);
           mul[nr,1]:=ii;
           mul[nr,2]:=jj;
           mul[nr,3]:=(y[jj+1]-y[ii])*(x[lin+1]-x[mul[i,4]]);
           mul[nr,4]:=mul[i,4];
           mul[nr,5]:=lin;
           loc[ii]^[jj]:=nr;
           mat[ii]^[jj]:=mul[nr,3];
         end;
end;

procedure react;
begin
  if mul[i,3]=opt then inc(nrs)
     else if mul[i,3]>opt then
          begin
            nrs:=1;
            opt:=mul[i,3];
          end;
end;

procedure rezolva;
begin
  nr:=0;
  fillchar(mul,sizeof(mul),0);
  for lin:=1 to m+1 do
      begin
        makelin;
        i:=1;
        while i<=nr do
          begin
            if v[mul[i,1]]>=mul[i,2] then
               begin
                 if mul[i,5]<>lin then
                 inc(mul[i,3],d[mul[i,2]]-d[mul[i,1]-1])
               end
               else
               begin
                 baga;
                 if mul[i,3]>=opt then react;
                 loc[mul[i,1]]^[mul[i,2]]:=0;
                 mat[mul[i,1]]^[mul[i,2]]:=0;
                 mul[i]:=mul[nr];
                 mul[nr,1]:=0;
                 mul[nr,2]:=0;
                 mul[nr,3]:=0;
                 mul[nr,4]:=0;
                 mul[nr,5]:=0;
                 loc[mul[i,1]]^[mul[i,2]]:=i;
                 dec(nr);
                 dec(i);
               end;
            inc(i);
          end;
        for i:=1 to n do
            if (a[lin]^[i]<>0)and(a[lin]^[i-1]=0) then
               begin
                 j:=i;
                 while a[lin]^[j+1]<>0 do inc(j);
                 if mat[i]^[j]=0 then
                    begin
                      inc(nr);
                      mul[nr,1]:=i;
                      mul[nr,2]:=j;
                      mul[nr,3]:=d[j]-d[i-1];
                      mul[nr,4]:=lin;
                      mul[nr,5]:=lin;
                      loc[i]^[j]:=nr;
                      mat[i]^[j]:=mul[nr,3];
                    end;
               end;
      end;
end;

procedure solve;
begin
  if nro<0 then exit;
  makexy;
  sort;
  constrmatr;
  fillmatr;
  rezolva;
  inc(nrteste);
  if nrteste mod 20=0 then
     begin
       writeln('Apasati o tasta pentru stergerea ecranului ');
       readkey;
       clrscr;
     end;
  writeln('Aria maxima=',opt,'.Numarul solutiilor=',nrs);
  writeln(fo,'Aria maxima=',opt,'.Numarul solutiilor=',nrs);
end;

begin
  writeln;
  writeln('Rezultatele vor fi scrise atat pe ecran, cat si in fisierul HAMBAR.OUT');
  assign(fi,'hambar.in');
  assign(fo,'hambar.out');
  reset(fi);
  rewrite(fo);
  for i:=0 to 100 do
      new(a[i]);
  for i:=0 to 100 do
      for j:=0 to 100 do
          a[i]^[j]:=0;
  for i:=0 to 100 do
      new(loc[i]);
  for i:=0 to 100 do
      for j:=0 to 100 do
          loc[i]^[j]:=0;
  for i:=0 to 100 do
      new(mat[i]);
  for i:=0 to 100 do
      for j:=0 to 100 do
          mat[i]^[j]:=0;
  while not seekeof(fi)do
    begin
      readdata;
      solve;
    end;
  close(fi);
  close(fo);
end.
==============================================================================
